#include <vector>
#include <queue>

using namespace std;

// 地图分析
// 你现在手里有一份大小为 n x n 的 网格 grid
// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/

class Solution 
{
private:
	static const int MAXN = 101;
	static const int MAXM = 101;
    
    int q[MAXN * MAXM][2];
    int l, r;
    bool visited[MAXN][MAXN];

    // 0 : 上，1 : 右，2 : 下，3 : 左
    // (x,y)  i 来到 0 位置 : x + move[i], y + move[i+1] -> x - 1, y
	// (x,y)  i 来到 1 位置 : x + move[i], y + move[i+1] -> x, y + 1
	// (x,y)  i 来到 2 位置 : x + move[i], y + move[i+1] -> x + 1, y
	// (x,y)  i 来到 3 位置 : x + move[i], y + move[i+1] -> x, y - 1
    int move[5] = { -1, 0, 1, 0, -1 };

public:
    int maxDistance(vector<vector<int>>& grid) 
    {
        l = r = 0;
        int m = grid.size(), n = grid[0].size();
        int seas = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                // 0 : 海洋  1 : 陆地
                if(grid[i][j] == 1)
                {
                    visited[i][j] = true;
                    q[r][0] = i;
                    q[r++][1] = j;
                }
                else
                {
                    visited[i][j] = false;
                    ++seas;
                }
            }
        }

        // 全是海洋或者全是陆地，返回 -1
        if(seas == 0 || seas == m * n) return -1;

        int level = 0;
        while(l < r)
        {
            ++level;
            int size = r - l;
            // 一层一层地遍历
            while(size--)
            {
                int x = q[l][0], y = q[l++][1];
                // 上、右、下、左
                for(int k = 0; k < 4; ++k)
                {
                    int nx = x + move[k], ny = y + move[k + 1];
                    // visited 数组可以使用 grid 来代替
                    if(nx >= 0 && nx < m && ny >= 0 && ny < m && !visited[nx][ny])
                    {
                        visited[nx][ny] = true;
                        q[r][0] = nx, q[r++][1] = ny;
                    }
                }
            }
        }
        return level - 1;
    }
};


class Solution 
{
public:
    int maxDistance(vector<vector<int>>& grid) 
    {
        int ret = 1, n = grid.size();
        queue<pair<int, int>> q;
        // 0 : 海洋  1 : 陆地
        int seas = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j])
                    q.push({i, j}); // 多源 BFS
                else
                    ++seas;
            }
        }

        // 网格是全 1 或者 全 0
        if(seas == 0 || seas == n * n) return -1;

        int dx[4] = {0, 0, -1, 1};
        int dy[4] = {-1, 1, 0, 0};
        while(!q.empty())
        {
            bool flag = false; // 有没有扩展出新的位置
            int m = q.size();
            while(m--)
            {
                auto [x, y] = q.front();
                q.pop();
                for(int k = 0; k < 4; ++k)
                {
                    int nx = x + dx[k], ny = y + dy[k];
                    // grid 充当 visited 的角色
                    if(nx >= 0 && nx < n && ny >= 0 && ny < n && !grid[nx][ny])
                    {
                        q.push({nx, ny});
                        grid[nx][ny] = ret; // 标记已经访问过了该位置
                        flag = true;
                    }
                }
            }
            if(flag) ++ret;
        }
        
        return ret - 1;
    }
};